package leetcode100

// TODO 递归+回溯 | 深度优先遍历 【-】 电话号码的字母组合
// TODO https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solution/hui-su-bu-hui-xie-tao-lu-zai-ci-pythonja-3orv/

var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) (ans []string) {
	n := len(digits)
	if n == 0 {
		return
	}
	path := make([]byte, n)
	var dfs func(int)
	dfs = func(i int) {
		// 回溯结束控制器
		if i == n {
			ans = append(ans, string(path))
			return
		}
		// 深度优先遍历
		for _, c := range mapping[digits[i]-'0'] {
			path[i] = byte(c)
			dfs(i + 1)
		}
	}
	dfs(0)
	return
}
